package problem86;

//86.分隔链表
//https://leetcode.cn/problems/partition-list/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head == null) return head;
        ListNode newHead = new ListNode();
        newHead.next = head;
        //找到第一个大于等于x的节点
        ListNode prevFlag = newHead;
        ListNode flag = head;
        while(flag != null && flag.val < x) {
            prevFlag = flag;
            flag = flag.next;
        }

        //此时链表的所有节点都比x小, 直接返回即可
        if(flag == null) return head;

        //遍历flag后面的节点, 比x小的节点插在flag前
        ListNode prevCur = flag;
        ListNode cur = flag.next;
        while(cur!=null) {
            if(cur.val < x) {
                ListNode next = cur.next;
                prevCur.next = next;
                prevFlag.next = cur;
                cur.next = flag;
                prevFlag = prevFlag.next;
                cur = next;
            }else {
                prevCur = cur;
                cur = cur.next;
            }
        }
        return newHead.next;
    }
}